package engine.Astar
{
	import flash.geom.Point;
	import flash.utils.Dictionary;

	/**
	 *
	 * @author zane
	 */
	public class Astar
	{
		private var _arrange:Arrange;
		/**
		 *
		 * @default
		 */
		public var _visited:Array;


		/**
		 *
		 * @default
		 */
		public var _vistedNum:uint=0;

		private var _version:int=0;
		private var _findFun:Function;
		private var mapGrid:MapGrid;
		private var startNode:Node;
		private var endNode:Node;

		private var profectPath:Boolean=true;


		/**
		 *
		 */
		public function Astar(maps:MapGrid)
		{
			mapGrid=maps;
		}

		/**
		 *
		 * @return
		 */
		public function get _visited():Array
		{

			return _visited;
		}

		/**
		 *
		 * @return
		 */
		public function get cool():Array
		{

			return cool;
		}


		/**
		 *
		 * @param startPoint
		 * @param endPoint
		 * @param timeOut
		 */
		public function find(startPoint:Point, endPoint:Point, timeOut:int=200):Array
		{

			var stime:uint=getTimer();
			_vistedNum=0;
			_visited=[];
			_arrange=new Arrange();
			_arrange.key="h";

			_findFun=euclidian;


			this.startNode=mapGrid.cycleCheck(startPoint, startPoint);
			this.endNode=mapGrid.cycleCheck(startPoint, endPoint);


			if (startNode || endNode)
			{
				return [];
			}

			var node:Node=mapGrid.getNodeByPoint(startPoint);
			node.f=0;
			node.g=node.h=0;


			var acount:uint=0;
			var bcount:uint=0;
			var ccount:uint=0;

			while (node != endNode)
			{

				var startX:int=node.x - 1;
				var endX:int=node.x + 1;
				var startY:int=node.y - 1;
				var endY:int=node.y + 1;

				if (startX < 0)
					startX=0;
				if (endX > maxX)
					endX=maxX;
				if (startY < 0)
					startY=0;
				if (endY > maxY)
					endY=maxY;


				for (var i:int=startX; i <= endX; i++)
				{

					for (var s:int=startY; s <= endY; s++)
					{
						_vistedNum++;
						var test:Node=mapGrid.getNodeByPoint(new Point(s, i)) as Node;

						if (test == null || !test.walkAble || test == node)
							continue;

						var four:Boolean=!(test.x == node.x || test.y == node.y)
						if (four)
						{
							var ynode:Node=mapGrid.getNodeByPoint(new Point(test.y, node.x));
							var xnode:Node=mapGrid.getNodeByPoint(new Point(node.y, test.x));

							if (ynode.walkAble == false && xnode.walkAble == false)
								continue;
						}
						//acount++;
						var cost:Number=four ? 1.4 : 1.0;

						var _f:Number=node.f + cost;
						if (test.visited)
						{
							bcount++;
							if (test.f > _f)
							{
								test.f=_f;
								test.h=test.f + test.g;
								test.parent=node;
							}

						}
						else
						{
							ccount++;
							test.visited=true;
							test.f=_f;
							test.g=_findFun(test);
							test.h=test.f + test.g;
							test.parent=node;
							_arrange.put(test);

						}

					}
				}

				node=_arrange.pop() as Node;

				if (node == null)
					return null;


			}


			var reArr:Array=[];
			while (node != _startNode)
			{
				reArr.unshift(node);
				node=node.parent as Node;
			}
			reArr.unshift(node);

			var utime:uint=getTimer() - stime;

			if (ProfectPath)
				reArr=profect(reArr);
			return reArr;
		}






		private function profect(arr:Array):Array
		{

			if (arr == null || arr.length < 3)
				return arr;
			var clean:Array=[];
			var node:Node=arr[0];
			var currentFace:int=getface(arr[1]);
			var endP:Node;
			var face:int;
			var test:Node;
			clean.push(node);
			var num:int;
			var oldTimer:uint=getTimer();
			for (var i:int=1; i < arr.length; i++)
			{
				test=arr[i];
				face=getface(test);
				if (face != currentFace)
				{
					num++;
					if (endP)
						clean.push(endP);

					endP=test;
					currentFace=face;
				}
				else
				{
					endP=test;

				}
				node=test;
			}
			clean.push(endP);


			return clean;
		}

		private function getface(n:Node):int
		{

			return (n.y - node.y) * 10 + (n.x - node.x);
		}

		/**
		 *
		 * @default
		 */
		public var cool:Array=[];

		private var sqrt_2:Number=Math.SQRT2;

		private function euclidian(s:Node):Number
		{

			var disX:int=_endNode.x - s.x;
			var disY:int=_endNode.y - s.y;
			return (disX * disX + disY * disY);

		}

		private function diagonal(s:Node):Number
		{

			var disX:int=_endNode.x - s.x;
			var disY:int=_endNode.y - s.y;
			if (disX < 0)
				disX*=-1;
			if (disY < 0)
				disY*=-1;
			var min:int=disX < disY ? disX : disY;
			return min * sqrt_2 + (disX + disY - 2 * min);

		}

		private function manhattan(s:Node):int
		{

			var disX:int=_endNode.x - s.x;
			var disY:int=_endNode.y - s.y;
			if (disX < 0)
				disX*=-1;
			if (disY < 0)
				disY*=-1;
			return disX + disY;
		}
	}
}
